Kosaraju's algorithm

contents

타잔 알고리즘이 한 번의 패스로 해결하는 반면, 코사라주 알고리즘은 두 번의 DFS 패스를 사용합니다. 그래프 방향에 대한 매우 단순한 기하학적 성질을 이용하기 때문에 개념적으로 이해하기는 훨씬 쉽다고 평가받습니다.

1. 핵심 직관

이 알고리즘은 SCC의 근본적인 성질을 이용합니다.

그래프의 모든 간선 방향을 뒤집으면(전치 그래프, Transpose Graph $G^T$), 강하게 연결된 요소(SCC) 자체는 변하지 않고 그대로 유지됩니다.

하지만, SCC들 사이 의 연결 방향은 반대가 됩니다.

• 원본 그래프 $G$: $SCC_1 \to SCC_2$
• 전치 그래프 $G^T$: $SCC_2 \to SCC_1$

원본 그래프에서 DFS를 수행하여 "탐색 종료 시간(Finishing Time)"을 구하고, 그 순서대로 역방향 그래프에서 다시 DFS를 수행하면, 의존성 체인의 "끝"에서부터 SCC를 하나씩 떼어낼 수 있게 됩니다.

2. 알고리즘 (2-Pass 방식)

1단계: 종료 시간 계산 (Finishing Times)

원본 그래프 $G$에 대해 표준 DFS를 수행합니다.

• 우리는 노드에 들어가는 시간은 신경 쓰지 않습니다. 노드 방문을 마치는(Finish) 시간(즉, 재귀 호출에서 돌아오는 시점)이 중요합니다.
• 각 노드의 방문이 끝날 때마다, 그 노드를 스택(Stack) 넣습니다.
• 결과: 스택의 맨 위에 있는 노드는 가장 늦게 방문이 끝난 노드입니다. 이 노드는 "소스 SCC"(다른 SCC로 나가는 간선은 있지만 들어오는 간선은 없는 SCC)에 속해 있을 가능성이 높습니다.

2단계: SCC 추출

1. 전치 그래프(Transpose Graph) $G^T$를 계산합니다(모든 간선의 방향을 뒤집습니다).
2. 1단계에서 채워진 스택에서 노드를 하나씩 꺼냅니다(Pop).
3. 만약 꺼낸 노드 $u$가 이번 패스에서 아직 방문하지 않은 노드라면:
   • 전치 그래프 $G^T$ 상에서 $u$를 시작점으로 DFS를 수행합니다.
   • 이 역방향 그래프에서 $u$로부터 도달 가능한 모든 노드들이 하나의 강하게 연결된 요소(SCC) 를 형성합니다.
   • 이들을 방문 처리하고 출력합니다.

3. 트레이스 예제

그래프: $0 \to 1 \to 2 \to 0$ (사이클 A) 그리고 $1 \to 3$ (노드 B).

간선: $(0,1), (1,2), (2,0), (1,3)$.

1단계: 원본 그래프 DFS

0에서 DFS를 시작한다고 가정합시다.

1. DFS(0)이 DFS(1) 호출.
2. DFS(1)이 DFS(2) 호출 (3보다 2를 먼저 선택했다고 가정).
3. DFS(2)는 0을 봄 (이미 방문함). 반환(Return). 2 종료. 스택에 2 넣기. 스택: [2]
4. DFS(1)로 복귀. DFS(3) 호출.
5. DFS(3)은 이웃 없음. 반환. 3 종료. 스택에 3 넣기. 스택: [2, 3]
6. DFS(1) 종료. 스택에 1 넣기. 스택: [2, 3, 1]
7. DFS(0) 종료. 스택에 0 넣기. 스택: [2, 3, 1, 0]

스택 (위에서 아래로): 0, 1, 3, 2

2단계: 전치 그래프($G^T$) DFS

뒤집힌 간선: $(1,0), (2,1), (0,2), (3,1)$.

1. 0 꺼냄(Pop). 미방문 상태. DFS_Rev(0) 시작.
   • 0에서 2로 이동 ($0 \to 2$).
   • 2에서 1로 이동 ($2 \to 1$).
   • 1에서 3으로? 간선은 $3 \to 1$이므로 못 감. 1에서 0은 이미 방문함.
   • DFS_Rev 수집 결과: {0, 2, 1}.
   • 첫 번째 SCC 발견: {0, 1, 2}.
2. 1 꺼냄. 이미 방문함. 건너뜀.
3. 3 꺼냄. 미방문 상태. DFS_Rev(3) 시작.
   • 3에서 1로? 간선은 $3 \to 1$이지만 1은 이미 방문함.
   • DFS_Rev 수집 결과: {3}.
   • 두 번째 SCC 발견: {3}.
4. 2 꺼냄. 이미 방문함. 건너뜀.

결과: SCC는 {0, 1, 2}와 {3}입니다.

4. 구현 코드 (Java)

import java.util.*;

public class KosarajuSCC {
    private int V;
    private List> adj;

    public KosarajuSCC(int V) {
        this.V = V;
        adj = new ArrayList<>();
        for (int i = 0; i < V; ++i)
            adj.add(new ArrayList<>());
    }

    public void addEdge(int v, int w) {
        adj.get(v).add(w);
    }

    // 1단계: 종료 시간 순서대로 스택 채우기
    private void fillOrder(int v, boolean visited[], Stack stack) {
        visited[v] = true;
        for (int n : adj.get(v)) {
            if (!visited[n])
                fillOrder(n, visited, stack);
        }
        stack.push(v); // 자식 방문 후(종료 시점)에 스택에 넣음
    }

    // 2단계: 전치 그래프에서 DFS
    private void DFSUtil(int v, boolean visited[], List component, List> transposeAdj) {
        visited[v] = true;
        component.add(v);
        for (int n : transposeAdj.get(v)) {
            if (!visited[n])
                DFSUtil(n, visited, component, transposeAdj);
        }
    }

    // 메인 알고리즘
    public List> getSCCs() {
        Stack stack = new Stack<>();
        boolean visited[] = new boolean[V];

        // 1. 스택 채우기 (첫 번째 DFS 패스)
        for (int i = 0; i < V; i++) {
            if (!visited[i])
                fillOrder(i, visited, stack);
        }

        // 2. 전치 그래프 생성
        List> transposeAdj = new ArrayList<>();
        for (int i = 0; i < V; i++) transposeAdj.add(new ArrayList<>());
        for (int v = 0; v < V; v++) {
            for (int neighbor : adj.get(v)) {
                transposeAdj.get(neighbor).add(v); // 방향 뒤집기
            }
        }

        // 3. 스택 처리 (두 번째 DFS 패스)
        Arrays.fill(visited, false); // 방문 배열 초기화
        List> sccs = new ArrayList<>();

        while (!stack.empty()) {
            int v = stack.pop();
            if (!visited[v]) {
                List component = new ArrayList<>();
                DFSUtil(v, visited, component, transposeAdj);
                sccs.add(component);
            }
        }
        return sccs;
    }
}

5. 왜 작동하는가? (로직의 원리)

SCC들 간의 관계(압축 그래프)가 $A \to B$라고 상상해 봅시다.

즉, SCC $A$의 어떤 노드에서 SCC $B$의 어떤 노드로 가는 간선이 있다는 뜻입니다.

1. 1단계 (종료 시간):
   • 만약 DFS가 $A$에서 시작하면, $B$로 이동하여 $B$를 완전히 끝내고 스택에 넣은 뒤, $A$로 돌아와 $A$를 끝내고 스택에 넣습니다. 스택 상단: A.
   • 만약 DFS가 $B$에서 시작하면, $A$로 갈 수 없습니다. $B$를 끝내고 스택에 넣습니다. 나중에 $A$를 방문하고 스택에 넣습니다. 스택 상단: A.
   • 핵심 통찰: "소스(Source)" 역할의 SCC($A$ 같은)에 있는 노드들은 항상 "싱크(Sink)" 역할의 SCC($B$ 같은) 노드들보다 스택의 더 위쪽 에 위치하게 됩니다.
2. 2단계 (역방향 그래프 $B \to A$):
   • 스택에서 $A$를 먼저 꺼냅니다.
   • 역방향 그래프에서는 간선이 $B \to A$입니다.
   • $A$에서 DFS를 시작하면 $A$ 안에 갇히게 됩니다. $B$로 갈 수 없습니다(역방향 간선이 없으므로).
   • 따라서 DFS는 정확히 $A$ 컴포넌트만 분리해 냅니다.

6. 복잡도 분석

요약 비교: 코사라주 vs. 타잔

references